Selection


What's Selection?

	finding the kth smallest item
	special case is median (n/2th smallest item)


How can you use sorting to solve the selection problem?

	sort and return item in position k


What's the Big-Oh bound for this solution?

	N log N
	can do better



Quickselect


How does Quickselect work?

	almost like quicksort
	pick a pivot
	partition the items
	recurse only on side where kth item is located


What's the Big-Oh bound for Quickselect?

	time is linear




Lower Bound for Sorting


Is it possible to sort faster than O(n log n)?

	yes using array indexing
	only works for restricted types (integers)


Is it possible for comparison-based algorithms?

	no
	any comparison-based sort must use N log N compares
	must choose between N! permutations
	each compare step divides problem in half
	log N! steps to arrive at 1 permutation
	O(log N!) is the same BigOh as O(N log N)